import sys
import shelve

from threading import Lock, Thread
import threading
import time
import math
from Queue import Queue

import salsa
from salsa import do_trace_exception

from salsa.util import LoggerSeverity
from salsa.service import Client
from salsa.service.stree import SourceTree, SourceState
from salsa.util.thread import ThreadPool

PROGRESS_THRESHOLD = 250
DEPTREE_TRACE = False

class Source:        
    def __init__(self, id):
        self.deps = []  # Our dependencies
        self.rdeps = [] # Our dependents 
        
        self.initialized = False
        self.failed = False
        self.invalidated = False
        self.dirty = False
        
        # For loop detection
        self.depth = None
        
        self.id = id
    
    def set(self, id, name, state, failmsg):
        '''Set us source information from stree database'''
        self.initialized = True
        
        self.name = name
        self.state = state
        
        if self.state == SourceState.S_FAILED:
            self.failed = True
    
    def add(self, src):
        '''Add dependency self->src'''
        self.deps.append(src)
        src.rdeps.append(self)
    
    def remove_r(self, src):
        if src in self.rdeps:
            src.deps.remove(self)
            self.rdeps.remove(src)
    
    def remove(self, src):
        if src in self.deps:
            src.rdeps.remove(self)
            self.deps.remove(src)
    
    def invalidate(self, recheck=False):
        '''Check if this Source is failed and invalidate
        all dependent sources
        
        @param recheck means that invalidate() ignores internal 
        flag invalidated and rechecks reverse-dependency tree
        
        Recursive.'''
        # No need to invalidate, already did
        # that during recursive call
        if self.invalidated and not recheck:
            return
        
        self.invalidated = True
        
        if self.failed:
            print '%s is failed' % self.name
            
            for rdep in self.rdeps:
                rdep.failed = True
                rdep.invalidate(recheck)
        
    
    def resolve_loop(self):
        '''Walks over depedndency tree and sets marks (depth) for each node that it 
        passes by. 
        
        This is need for correct work of topological sorting'''
        # Calculate depth if needed
        if self.depth == None:
            self.calc_depth()
        
        for dep in self.deps[:]:
            # All dependencies must be deeper than us
            if dep.depth < self.depth:
                salsa.logger.log(LoggerSeverity.LS_WARNING, 'Dependency loop was resolved: %s -> %s' % (self, dep)) 
                self.remove(dep)
                
        for rdep in self.rdeps[:]:
            if rdep.depth > self.depth:
                salsa.logger.log(LoggerSeverity.LS_WARNING, 'Dependency loop was resolved: %s -> %s' % (rdep, self))
                self.remove_r(rdep)
    
    def calc_depth(self):
        '''Calculate depth for this node and all it's dependencies and dependants
        
        If we meet node that already has calculated depth, update it if new value looks deeper
        than old one and don't follow it's deps/rdeps. It may be loop and may not, so calculate
        all depths than compare them in resolve_loop'''
        # list of tasks: tuples (source, index, previous source)
        tasks = [(self, 0, None)]
        
        while tasks:
            src, depth, prev_src = tasks.pop(0)
            
            # First time set depth
            if src.depth == None:
                src.depth = depth
            else:
                if abs(depth) > abs(src.depth):
                    # May be a loop, so ignore dependencies but update depth
                    src.depth = depth
                continue
            
            # Also because we walking both dep and rdep path
            # We may loop: prev_src->prev_src.deps->src->src.rdeps->prev_src
            # So we are crossing out this path by if
            walk = map(lambda x: (depth + 1, x), src.deps) + \
                    map(lambda x: (depth - 1, x), src.rdeps)
            
            for (new_depth, dep) in walk: 
                if dep is not prev_src:
                    # print '%d %s<->%s<->%s' % (new_depth, prev_src, src, dep)
                    tasks.append((dep, new_depth, src))
    
    def update_state(self, new_state):
        '''Updates state of source. If new state is FAILED - invalidate all dependent sources'''
        self.state = new_state
        
        if new_state == SourceState.S_FAILED:
            self.failed = True
            
            self.invalidate(recheck=True)
        
    
    def __cmp__(self, other):
        return self.id.__cmp__(other.id)
    
    def __str__(self):
        return self.name
    
    def __repr__(self):
        return '<Source: %s>' % (self.name)

class DependencyTree:
    '''Builds tree of sources based on their dependencies, sort it
    according to them'''
    
    class Error(Exception):
        pass
    
    class StreeClientSobj(Client):
        def __init__(self):
            self.stree = Client('svc.stree', SourceTree)
        
        def stop(self):
            self.stree.stop()
    
    class Resolver(Thread):
        '''Helper, that resolves dependencies for source
        
        Implemented as thread to keep stree service busy
        (stree is actually bottleneck because of sqlite3 implementation)'''
        def __init__(self, deptree, src):
            self.deptree = deptree
            self.src = src
            
            Thread.__init__(self, name = threading._newname('Adder-%d'))
            
            self.daemon = True
        
        def sobj_attach(self, sobj):
            self.stree = sobj.stree
        
        def run(self):
            try:
                deps = self.stree.get_deps(self.src.id)
        
                for (srcid, ) in deps:
                    dep_src = self.deptree.get_source(srcid)
                    
                    self.src.add(dep_src)
                
                # print '%s is resolved' % self.src.name
            finally:
                self.deptree.resolvers.notify()                
    
    def __init__(self):
        self.stree = Client('svc.stree', SourceTree)
        self.sources = {}
        self.src_lock = Lock()
        
        self.deps_cache = None
        
        # Sorted list of sources according to it's 
        # dependencies
        self.sourcelist = []
    
    def get_source(self, srcid):
        '''Gets source from sources dict
        
        If not yet created (i.e. creating dependency), costructs
        a new Source object. '''
        with self.src_lock:
            if srcid in self.sources:
                src = self.sources[srcid]
            else:
                src = Source(srcid)
                self.sources[srcid] = src 
            
            return src
    
    def add_source(self, srcdef):
        srcid = srcdef[0]
        src = self.get_source(srcid)        
        
        src.set(*srcdef)
        
        # print '%s is added: %d' % (src.name, src.id)
        
        # if str(srcid) not in self.deps_cache:
        resolver = DependencyTree.Resolver(self, src)
        self.resolvers.dispatch(resolver)
    
    def create_tree(self, num_resolvers = 12):
        walker = self.stree.walk_tree()
        added_num = 0
        
        self.resolvers = ThreadPool(num_resolvers, sobj_class = DependencyTree.StreeClientSobj)
        
        salsa.logger.log(LoggerSeverity.LS_INFO, 'Building dependency tree...')
        
        _start = time.clock()
        for src in walker:
            self.add_source(src)
            
            added_num += 1
            if added_num % PROGRESS_THRESHOLD == 0:
                salsa.logger.log(LoggerSeverity.LS_NOTICE, 'Added %d sources so far' % added_num)
            
        self.resolvers.join()
        _end = time.clock()
        
        salsa.logger.log(LoggerSeverity.LS_INFO, 'Building dependency tree took %f seconds' % (_end - _start))
    
    def invalidate(self):
        salsa.logger.log(LoggerSeverity.LS_INFO, 'Invalidating faulty paths...')
        
        _start = time.clock()
        
        # Set failed status to all dependent sources according to it's states
        for src in self.sources.itervalues():
            src.invalidate()
        
        # Filter failed sources
        old_sources_num = len(self.sources)
        self.sources = dict((id, src) 
                            for (id, src)
                            in self.sources.items() 
                            if not src.failed)
        new_sources_num = len(self.sources)
        
        _end = time.clock()
        
        salsa.logger.log(LoggerSeverity.LS_INFO, 'Invalidating took %f seconds, was %d sources, now %d sources' % 
                                    ((_end - _start), old_sources_num, new_sources_num) )
    
    def postprocess(self):
        self.invalidate()
        
        salsa.logger.log(LoggerSeverity.LS_INFO, 'Topological sorting')
        
        _start = time.clock()
        
        for src in self.sources.itervalues():
            src.resolve_loop()
            
            # Save copies of rdeps that are used in topological 
            # sorting to track roots
            src.ts_rdeps = src.rdeps[:]
            src.ts_deps = src.deps[:]
        
        success = self.topological_sort()
        
        for src in self.sources.itervalues():
            src.rdeps = src.ts_rdeps
            src.deps = src.ts_deps 
        
        _end = time.clock()
        
        if not success:
            salsa.logger.log(LoggerSeverity.LS_CRITICAL, 'Topological sorting was not successful');
            self.dump()
        
        salsa.logger.log(LoggerSeverity.LS_INFO, 'Topological sorting took %f seconds' % (_end - _start))
        
        fuuu = lambda src: not (src.state == SourceState.S_PARSED or src.failed)
        self.sourcelist = filter(fuuu, self.sourcelist)
    
    def topological_sort(self):
        roots = []
        num_edges = 0
        
        for src in self.sources.itervalues():
            if len(src.deps) == 0:
                roots.append(src)
                
                # print 'R+', str(src)
            
            num_edges += len(src.deps)
        
        while roots:
            # Act like deque
            src = roots.pop(0)
            
            self.sourcelist.append(src)
            
            if len(self.sourcelist) % PROGRESS_THRESHOLD == 0:
                salsa.logger.log(LoggerSeverity.LS_INFO, 'Sorted %d sources so far' % len(self.sourcelist))
            
            for rdep in src.rdeps[:]:
                # Delete edge
                src.remove_r(rdep)
                
                num_edges -= 1
                
                # Was last dependency
                if len(rdep.deps) == 0:
                    roots.append(rdep)
                    
                    # print 'R+', str(rdep)
        
        # Topological sorting is successfully completed
        # if no edges left in dependency tree
        return num_edges == 0 
                
    def dump(self):
        for src in self.sources.itervalues():
            print'-->%s' % src
            
            for dep in src.deps:
                print '\tD %s' % dep
            
            for dep in src.rdeps:
                print '\tR %s' % dep
    
    def dump_source_list(self):
        src_list_path = salsa.core.abs_data_path('sourcelist.txt')
        src_list_file = open(src_list_path, 'w')
        
        for src in self.sourcelist:
            print >> src_list_file, str(src.id) + ',' + src.name
    
    def stop(self):
        self.resolvers.join()
        
        self.stree.stop()